package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/top-k-frequent-elements/">前 K 个高频元素(Top K Frequent Elements)</a>
 * <p>给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: nums = [1,1,1,2,2,3], k = 2
 *      输出: [1,2]
 *
 * 示例 2:
 *      输入: nums = [1], k = 1
 *      输出: [1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>1 <= nums.length <= 10^5</li>
 * <li>k 的取值范围是 [1, 数组中不相同的元素的个数]</li>
 * <li>题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的</li>
 * </ul>
 * </p>
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 *
 * @author c2b
 * @since 2023/11/7 15:35
 */
public class LC0347TopKFrequentElements_M {
    static class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
            Map<Integer, Integer> value2frequentMap = new HashMap<>();
            for (int currNum : nums) {
                Integer freq = value2frequentMap.getOrDefault(currNum, 0);
                value2frequentMap.put(currNum, freq + 1);
            }
            // 小根堆：按照在map中出现的频次排序。
            // int[]-0：元素值，int[]-1：元素频次
            PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>((x, y) -> y.getValue() - x.getValue());
            for (Map.Entry<Integer, Integer> entry : value2frequentMap.entrySet()) {
                heap.offer(entry);
            }
            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = heap.poll().getKey();
            }
            return res;
        }

        public int[] topKFrequent2(int[] nums, int k) {
            // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
            Map<Integer, Integer> value2frequentMap = new HashMap<>();
            for (int currNum : nums) {
                Integer freq = value2frequentMap.getOrDefault(currNum, 0);
                value2frequentMap.put(currNum, freq + 1);
            }
            // 小根堆：按照在map中出现的频次排序。
            // int[]-0：元素值，int[]-1：元素频次
            PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
            for (Map.Entry<Integer, Integer> entry : value2frequentMap.entrySet()) {
                heap.offer(new int[]{entry.getKey(), entry.getValue()});
            }
            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = heap.poll()[0];
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2));
        Printer.printArrayInt(solution.topKFrequent(new int[]{1}, 1));
        Printer.printArrayInt(solution.topKFrequent(new int[]{3, 0, 1, 0}, 1));
        Printer.printArrayInt(solution.topKFrequent(new int[]{4, 1, -1, 2, -1, 2, 3}, 2));
        Printer.printArrayInt(solution.topKFrequent(new int[]{5, 2, 5, 3, 5, 3, 1, 1, 3}, 2));
    }
}
